package wuziqi;

import java.util.*;

// 极小化极大算法AI - 高级难度
class MinimaxAI implements AI {
    private int maxDepth;
    
    public MinimaxAI() {
        this.maxDepth = 3; // 搜索深度
    }
    
    public MinimaxAI(int depth) {
        this.maxDepth = depth;
    }
    
    @Override
    public int[] makeMove(GameState state, GameConfig config) {
        char[][] board = copyBoard(state.getBoard());
        char aiPlayer = state.getCurrentPlayer();
        char humanPlayer = (aiPlayer == config.getPlayer1Symbol()) ? 
                          config.getPlayer2Symbol() : config.getPlayer1Symbol();
        
        int[] bestMove = minimax(board, 0, true, aiPlayer, humanPlayer, 
                                Integer.MIN_VALUE, Integer.MAX_VALUE, config);
        return new int[]{bestMove[0], bestMove[1]};
    }
    
    private int[] minimax(char[][] board, int depth, boolean isMaximizing, 
                         char currentPlayer, char opponent, int alpha, int beta, GameConfig config) {
        // 终止条件：达到最大深度或游戏结束
        if (depth == maxDepth || isTerminal(board, config)) {
            return new int[]{-1, -1, evaluateBoard(board, currentPlayer, opponent, config)};
        }
        
        List<int[]> possibleMoves = getPossibleMoves(board, config);
        
        if (isMaximizing) {
            int[] bestMove = new int[]{-1, -1, Integer.MIN_VALUE};
            for (int[] move : possibleMoves) {
                board[move[0]][move[1]] = currentPlayer;
                int[] currentMove = minimax(board, depth + 1, false, opponent, currentPlayer, alpha, beta, config);
                board[move[0]][move[1]] = config.getEmptySymbol();
                
                if (currentMove[2] > bestMove[2]) {
                    bestMove[0] = move[0];
                    bestMove[1] = move[1];
                    bestMove[2] = currentMove[2];
                }
                
                alpha = Math.max(alpha, bestMove[2]);
                if (beta <= alpha) break; // Alpha-Beta剪枝
            }
            return bestMove;
        } else {
            int[] bestMove = new int[]{-1, -1, Integer.MAX_VALUE};
            for (int[] move : possibleMoves) {
                board[move[0]][move[1]] = currentPlayer;
                int[] currentMove = minimax(board, depth + 1, true, opponent, currentPlayer, alpha, beta, config);
                board[move[0]][move[1]] = config.getEmptySymbol();
                
                if (currentMove[2] < bestMove[2]) {
                    bestMove[0] = move[0];
                    bestMove[1] = move[1];
                    bestMove[2] = currentMove[2];
                }
                
                beta = Math.min(beta, bestMove[2]);
                if (beta <= alpha) break; // Alpha-Beta剪枝
            }
            return bestMove;
        }
    }
    
    private List<int[]> getPossibleMoves(char[][] board, GameConfig config) {
        List<int[]> moves = new ArrayList<>();
        int size = config.getBoardSize();
        char empty = config.getEmptySymbol();
        
        // 只考虑有棋子周围的空位（优化性能）
        Set<String> considered = new HashSet<>();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i][j] != empty) {
                    // 检查周围3x3区域
                    for (int di = -2; di <= 2; di++) {
                        for (int dj = -2; dj <= 2; dj++) {
                            int ni = i + di;
                            int nj = j + dj;
                            if (ni >= 0 && ni < size && nj >= 0 && nj < size && 
                                board[ni][nj] == empty) {
                                String key = ni + "," + nj;
                                if (!considered.contains(key)) {
                                    moves.add(new int[]{ni, nj});
                                    considered.add(key);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        // 如果棋盘很空，返回中心区域
        if (moves.isEmpty()) {
            int center = size / 2;
            for (int i = center - 1; i <= center + 1; i++) {
                for (int j = center - 1; j <= center + 1; j++) {
                    if (i >= 0 && i < size && j >= 0 && j < size && board[i][j] == empty) {
                        moves.add(new int[]{i, j});
                    }
                }
            }
        }
        
        return moves;
    }
    
    private boolean isTerminal(char[][] board, GameConfig config) {
        // 简化实现，实际应该检查胜负
        return false;
    }
    
    private int evaluateBoard(char[][] board, char player, char opponent, GameConfig config) {
        int score = 0;
        int winCount = config.getWinCount();
        
        // 评估所有可能的连线
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == player) {
                    score += evaluatePosition(board, i, j, player, opponent, winCount);
                } else if (board[i][j] == opponent) {
                    score -= evaluatePosition(board, i, j, opponent, player, winCount);
                }
            }
        }
        
        return score;
    }
    
    private int evaluatePosition(char[][] board, int row, int col, char player, char opponent, int winCount) {
        int score = 0;
        int[][] directions = {{0,1}, {1,0}, {1,1}, {1,-1}};
        
        for (int[] dir : directions) {
            score += evaluateDirection(board, row, col, dir[0], dir[1], player, opponent, winCount);
        }
        
        return score;
    }
    
    private int evaluateDirection(char[][] board, int row, int col, int rowDir, int colDir, 
                                 char player, char opponent, int winCount) {
        // 类似于ScoreBasedAI的实现，但更简化
        int consecutive = 1;
        int openEnds = 0;
        
        // 正向检查
        int r = row + rowDir;
        int c = col + colDir;
        int count = 0;
        
        while (isValidPosition(board, r, c) && count < winCount - 1 && board[r][c] == player) {
            consecutive++;
            r += rowDir;
            c += colDir;
            count++;
        }
        if (isValidPosition(board, r, c) && board[r][c] != opponent) {
            openEnds++;
        }
        
        // 反向检查
        r = row - rowDir;
        c = col - colDir;
        count = 0;
        
        while (isValidPosition(board, r, c) && count < winCount - 1 && board[r][c] == player) {
            consecutive++;
            r -= rowDir;
            c -= colDir;
            count++;
        }
        if (isValidPosition(board, r, c) && board[r][c] != opponent) {
            openEnds++;
        }
        
        // 评分逻辑
        if (consecutive >= winCount) return 10000;
        if (consecutive == winCount - 1 && openEnds > 0) return 1000;
        if (consecutive == winCount - 2 && openEnds > 0) return 100;
        return consecutive * 10 + openEnds * 5;
    }
    
    private boolean isValidPosition(char[][] board, int row, int col) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length;
    }
    
    private char[][] copyBoard(char[][] original) {
        char[][] copy = new char[original.length][];
        for (int i = 0; i < original.length; i++) {
            copy[i] = original[i].clone();
        }
        return copy;
    }
}